
import java.util.*;
public class ST {

	public static ArrayList<Node> nodeList; //array der indeholder alle nodes. bruges til debugging. Beh�ver nok ikke at bruge denne, da man bare kan kigge i cList i debuggeren.
	public Node root;
	int size;
	public ST(String s)
	{
		root = new Node("",null);
		size = 0;
		nodeList = new ArrayList<Node>();
		constructTree(s);
	}
	/*
	 * Denne følger meget konkret http://www.daimi.au.dk/~cstorm/courses/StrAlg_f10/slides/McCreight-2010.pdf 
	 * Algoritmen står meget beskrevet i midten af den pdf.
	 */
	public void constructTree(String input)
	{
		//add the entire string under the root.
		root.addChild(input);
	//	System.out.println("child with string "+input+" added under root");
		String headi;
		String headi2;
		Object[] hej;
		String vPart = "";
		Node currentNode = root;
		String taili;
		String currentString;
		root.setSuffixLink(root);
		Node w = new Node(null,null);
		for(int i = 1; i <= input.length(); i++)
		{
			if(i == input.length())
			{
				//jeg skal her bare indsætte $ under root, og derefter return
				w = new Node("$", root);
				root.addChild(w);
				System.out.println("returnerer med i = "+i);
				return; //jeg kan her returnere efter et givet antal iterationer af mit store forloop.
			}
		//	System.out.println("i = "+i);
			currentString = input.substring(i); //Dette er det suffix vi kigger på atm. (skal bruges til at regne tail).
			//System.out.println("currentString = "+currentString);
			headi = head(input,i);
			
			if(headi.length() == 0 ) //if head(i) ="" then
			{
				headi2 = head(input,i+1);//(headTail(input,i)[1]).substring(1); //jeg finder tail af input, og cutter det første tegn af. Dette er hvad jeg skal indsætte.

				if(headi2.length() == 0) // så skal den bare smides ind under root.
				{
					root.addChild(input.substring(i));
			//		System.out.println("child with string "+input.substring(i)+" added under root");
					continue;
				}
				else //så hvis vores head(i+1) ikke er "", så skal jeg gå head(i+1) ned i træet, og lave en knude her. Nu kan jeg smide tail på efter her.
				{
					//når jeg er her inde, skal jeg lave en knude mellem headi2 og dens tail. NOTE: tail er bare currentString.substring(headi2.length()).

			//		System.out.println("inserting headi2 = "+headi2);
			//		System.out.println("inserting tail = "+currentString.substring(headi2.length()));
					taili = currentString.substring(headi2.length());
					insert(headi2, currentString.substring(headi2.length()));
				}
			}
			else//headi != ""
			{
				/* u = parent(headi)  - kan bare kalde parent på den node. 
				 * v = label(u,head(i)) - dette er label MELLEM u og head(i). dvs. bare den streng der er gemt i head(i)
				 */

				//find den note, der repræcenterer head(i); Dette kan man gøre, bare ved at kigge roots børn igennem. Man kan godt risikere, at den ligger flere nodes under root.

				//System.out.println("headi = "+headi+ " for i = "+i);

				Node u = headiNode(headi).getParent();
				String v = headi;
				/*System.out.println("Node u = "+u);
				System.out.println("root = "+root);
				System.out.println("String v = "+v);*/
				
				/*
				 * NOTE: Fastscan: We may express the search for v starting at prefix node s(u) as:
						 w <- fastscan(s(u),v)
				 */
				if(u.getStr().length() != 0) //if u!=""
				{
					vPart = headiNode(headi).getStr(); // v = label(u,head(i)) 
					//System.out.println("vPart = "+vPart);
					currentNode = u.getSuffixLink();
				//	System.out.println("u.getStr() = "+u.getStr());
				//	System.out.println("u.Suffixlink.getSTr()"+u.getSuffixLink().getStr());
					//w = fastscan(s(u),v): aka fastscan(tempNode,v);
					//TODO: DEN FAILER HER, FORDI AT A IKKE F�R SAT DENS SUFFIXLINK
					for(int j = 0; j<currentNode.amountOfChildren();j++)
					{
						if(vPart.equals(""))
						{
							System.out.println("vPart == \"\", so w is root =)");
							break;
						}
						if(currentNode.cList.get(j).getStr().charAt(0) == vPart.charAt(0)) //hvis vi kigger ned i det rigtige barn.
						{
							currentNode = currentNode.cList.get(j);
							//da det er head jeg kigger på, skal jeg bare se, om currentNode er equal to, eller længere end cutString. If equal, har jeg fundet den rigtige node, eller substringer jeg, og kører igen.
							if(currentNode.getStr().length() == vPart.length())
							{
								break;
							}
							else if(currentNode.getStr().length() > vPart.length()) //jeg har fundet min node. vPart er over 0, s� denne kan jeg tjekke p� senere.
							{
								break;
							}
							else
							{
								vPart = vPart.substring(currentNode.getStr().length());
								j = 0;
								continue;
							}
						}
					}
					//System.out.println("currentNode.getStr() = "+currentNode.getStr());
					//System.out.println("vPart = "+vPart);
				}
				else //u == "". Vi skal her finde ud af om v er en node.
				{
					vPart = v.substring(1);
					//	System.out.println("vPart = "+vPart);
					currentNode = root;
					//w = fastscan("",v[2..|v|]) AKA. path fra root og ned til vPart.
					for(int j = 0; j<currentNode.amountOfChildren();j++)
					{
						if(vPart.equals(""))
						{
							//	System.out.println("vPart == \"\", so w is root =)");
							break;
						}
						if(currentNode.cList.get(j).getStr().charAt(0) == vPart.charAt(0)) //hvis vi kigger ned i det rigtige barn.
						{
							currentNode = currentNode.cList.get(j);
							
							//da det er head jeg kigger på, skal jeg bare se, om currentNode er equal to, eller længere end cutString. If equal, har jeg fundet den rigtige node, eller substringer jeg, og kører igen.
							if(currentNode.getStr().length() == vPart.length())
							{
								break;
							}
							else //eller skal jeg cutte af min cutString, og derefter prøve igen på currentNodes børn
							{
								vPart = vPart.substring(currentNode.getStr().length());
								j = 0;
								continue;
							}
						}
					}
					
					//efter det for-loop er currentNode den node som jeg skal stå i, eller den node, som jeg skal indsætte over. For at indsætte, skal jeg gå vPart ned i denne.
					//	System.out.println("currentNode == root "+ (currentNode == root));
					//System.out.println("vPart = "+vPart);
					
					//if w is an edge. DETTE betyder at vpart != "", da den ellers ville have stået i en knude
				}
				
				if(vPart.length() == 0) //if w is a node.
				{
					currentString = input.substring(i-1); //vi skal tage -1 her, fordi arrays starter på 0, mens "algoritmen" starter på 1
					headi = head(currentString,i-1); //vi skal tage -1 her, fordi arrays starter på 0, mens "algoritmen" starter på 1
					taili = currentString.substring(headi.length()); //slowscan fra w til tail(i). NOTE: tail er bare currentString.substring(headi2.length())

					//slowscan part
					String nodeString;
					String s = taili;
					boolean reset = false;
					boolean done = false;
					w = currentNode; //skal bruges senere til at adde suffixlink
					//System.out.println("w = "+w.getStr());
					
					//slowscan + add del
					for(int i2 = 0; i2<currentNode.amountOfChildren()+1; i2++) //+1 er et vammelt hack, for at få den til at køre en iteration mere
					{
						if(reset)
						{
							i2 = 0;
							reset = false;
						}
						if(done | currentNode.amountOfChildren() <= i2)
						{
							//System.out.println("breaker jeg her?");
							break;
						}

						nodeString = currentNode.cList.get(i2).getStr();
						//substring(i,j) sletter til og med i, men tager op til og med j

						for(int i3 = 0; i3<s.length();i3++) //kør igennem nodeString og tjek om tegnene passer sammen.
						{ 
							if(nodeString.charAt(i3) != s.charAt(0)) //hvis de ikke er ens, før jeg et nyt barn fra parent.
							{
								//System.out.println("i go in here?");
								break;
							}
							else
							{
								if(nodeString.length() > s.length()) //den her er god nok. Hvis strengen i nodes er længere end s, har jeg fundet min node. Nu skal jeg indsætte en node her.
								{
									//så skal jeg lave en node, og indsætte
									//denne skal inds�ttes p� kanten af en anden streng, og derfor skal der IKKE v�re $ med. Dette $ bliver senere indsat som et barn af denne node.
									if(s.contains("$") == true)
									{
										s = s.substring(0, s.length()-1);
									}
									Node lol = new Node(s,currentNode);
									currentNode.cList.get(i2).setStr(currentNode.cList.get(i2).getStr().substring(s.length())); //Jeg adder en knude mellem 2 knuder. Den nederste skal nu indeholde det den gjorde f�r - det som den midterste knude indeholder.
									lol.addChild(currentNode.cList.get(i2)); 
									currentNode.deleteChild(i2);
									currentNode.addChild(lol);
									lol.cList.get(0).setParent(lol);
									System.out.println("i = "+i);
									System.out.println("s = "+s);
									System.out.println("lol.cList.get(0).getStr() = "+lol.cList.get(0).getStr());
									lol.cList.get(0).setStr(lol.cList.get(0).getStr().substring(s.length())); //TODO: har fjernet -1 efter s.length(). (tidligere comment: -1 da s har $ på.)
									done = true;

									//add leaf i+1 and edge del. sidste linie i algo
									Node pew = new Node("$",lol);
									lol.addChild(pew);

								}
								else if(nodeString.length() < s.length()) //så skal jeg cutte af s, og opdatere min currentNode
								{
									//jeg ved her, at s.length() > nodeString.length, så mit loop kører på nodeString
									for(int l = 0; l<nodeString.length();l++)
									{
										if(s.charAt(0) == nodeString.charAt(l))
										{
											s = s.substring(1); //så cutter jeg en af s.
											//		System.out.println("får jeg cuttet af s?. s = "+s);
										}
									}
									currentNode = currentNode.cList.get(i2);
									reset = true;
									//når jeg når her ned, har jeg skåret hele nodeString fra s, og jeg kan breake mit indereste loop, og finde det nye barn
									break;
								}
							}							
						}
					} //lukker i2 forloop
					
					
				}//denne lukker if(vPart.length() == 0)
				else if(vPart.length() != 0) //jeg ved nu at w er en edge.
				{
					//add a node for w. Denne ligger vPart under currentNodes parent.
					w = new Node(vPart,currentNode.getParent());
					currentNode.setStr(currentNode.getStr().substring(vPart.length()));
					w.getParent().addChild(w);
					currentNode.setParent(w);
					w.addChild(currentNode);
					for(int k = 0;k<w.getParent().amountOfChildren();k++)
					{
						if(w.getParent().cList.get(k) == currentNode)
						{
							System.out.println("child k = "+k+" deleted");
							w.getParent().deleteChild(k);
						}
					}
					//add leaf i+1 and edge del. sidste linie i algo
					Node pew1 = new Node("$",w);
					w.addChild(pew1);
				}
				
				
				System.out.println("headi = "+headi);
				System.out.println("w.getStr() = "+w.getStr());
				headiNode(headi).setSuffixLink(w);
				System.out.println("hej");
			}
		} //denne lukker for-loop 
	}		

	
/*	public Object fastScan(Node from, String to)
	{
		String v = to;
		//	System.out.println("vPart = "+vPart);
		Node currentNode = from;
		Object returnObject = null;
		//w = fastscan("",v[2..|v|]) AKA. path fra root og ned til v.
		for(int j = 0; j<currentNode.amountOfChildren();j++)
		{
			if(v.equals(""))
			{
				//	System.out.println("vPart == \"\", so w is root =)");
				returnObject = from;
				break;
			}
			if(currentNode.cList.get(j).getStr().charAt(0) == v.charAt(0)) //hvis vi kigger ned i det rigtige barn.
			{
				currentNode = currentNode.cList.get(j);
				
				//da det er head jeg kigger på, skal jeg bare se, om currentNode er equal to, eller længere end cutString. If equal, har jeg fundet den rigtige node, eller substringer jeg, og kører igen.
				if(currentNode.getStr().length() == v.length())
				{
					break;
				}
				else //eller skal jeg cutte af min cutString, og derefter prøve igen på currentNodes børn
				{
					v = v.substring(currentNode.getStr().length());
					j = 0;
					continue;
				}
			}
			else //if u != ""
			{/*
				//	System.out.println("vPart == \"\", so w is root =)");
			break;
			}
			if(currentNode.cList.get(j).getStr().charAt(0) == vPart.charAt(0)) //hvis vi kigger ned i det rigtige barn.
			{
				currentNode = currentNode.cList.get(j);
				
				//da det er head jeg kigger på, skal jeg bare se, om currentNode er equal to, eller længere end cutString. If equal, har jeg fundet den rigtige node, eller substringer jeg, og kører igen.
				if(currentNode.getStr().length() == vPart.length())
				{
					break;
				}
				else //eller skal jeg cutte af min cutString, og derefter prøve igen på currentNodes børn
				{
					vPart = vPart.substring(currentNode.getStr().length());
					j = 0;
					continue;
				}
			}
		}
		return returnObject;
	}*/
	
	public Node headiNode(String head)
	{
		Node currentNode = root;
		String cutString = head;
		
		if(head.length() == 0) //if the head is 0, just return the root.
		{
			return currentNode;
		}
		for(int i = 0; i<currentNode.amountOfChildren();i++)
		{
			if(currentNode.cList.get(0) == null | cutString.length() == 0)
			{
				return null;
			}
			if(currentNode.cList.get(i).getStr().charAt(0) == cutString.charAt(0)) //hvis vi kigger ned i det rigtige barn.
			{
				currentNode = currentNode.cList.get(i);
				
				//da det er head jeg kigger på, skal jeg bare se, om currentNode er equal to, eller længere end cutString. If equal, har jeg fundet den rigtige node, eller substringer jeg, og kører igen.
				if(currentNode.getStr().length() == cutString.length())
				{
					return currentNode;
				}
				else //eller skal jeg cutte af min cutString, og derefter prøve igen på currentNodes børn
				{
					//System.out.println("currentNode.gesadasdsadtStr() = "+currentNode.getStr());
					//N�r jeg bruger length() til at cutte af min string, skal jeg s�rge for, at $ ikke t�ller med i l�ngden
					if(currentNode.getStr().contains("$") == true)//currentNode.getStr().charAt(currentNode.getStr().length()-1) == '$')
					{
						cutString = cutString.substring(currentNode.getStr().length()-1);
					}
					else
					{
						cutString = cutString.substring(currentNode.getStr().length());
					}
					i = 0;
					continue;
				}
			}
		}

		//something went very wrong. shouldnt be able to get down here.
		System.out.println("noget failede i min headiNode metode :(. Den burde ikke kunne komme her ned.");
		return null;

	}
	
	public void insert(String head, String tail)
	{
		Node currentNode = root;
		
		String cutString = head;
		for(int i = 0; i<currentNode.amountOfChildren();i++)
		{
			if(currentNode.cList.get(i).getStr().charAt(0) == cutString.charAt(0) ) //vi har fundet den af børnene vi skal kigge i. Hvis den aldrig kommer her ind, går den bare ned og returnerer
			{
				//jeg ved at min nye node skal indsættes cutString under currentNode. NOTE: værdien for en edge, står i den nederste af de 2 nodes.
				if(currentNode.cList.get(i).getStr().length() > cutString.length())
				{
					Node insertNodeTwo = new Node(head,currentNode);
					Node insertNode = new Node(tail,insertNodeTwo);
					currentNode.cList.get(i).setStr(currentNode.cList.get(i).getStr().substring(cutString.length()));
					currentNode.cList.get(i).setParent(insertNodeTwo);
					insertNodeTwo.addChild(currentNode.cList.get(i));
					insertNodeTwo.addChild(insertNode);
					currentNode.deleteChild(i);
					currentNode.addChild(insertNodeTwo);
					insertNode.setParent(insertNodeTwo);
					insertNodeTwo.setParent(currentNode);
					return;
				}
				else if(currentNode.cList.get(i).getStr().equals(cutString))
				{
					//jeg ved her, at jeg bare skal adde en node med strengen "$".
					currentNode.cList.get(i).addChild("$");
					System.out.println("added $ as child of "+currentNode.getStr());
					
					//TODO: jeg skal her huske at tjekke om den streng der ligger i currentNode er den samme som den streng i cutString!!!
					
					return;
				//	return null; //jeg kan nu kigge efter dette null i min metode over. Hvis jeg får et null tilbage, så er alle guuut.
				}
				else //jeg ved her, at jeg skal køre strengen igennem, og finde det barn, som jeg nu skal kigge inder. Jeg ved at cutString.length() > nodeString.length()
				{    // dvs, jeg bare skal bruge det rigtige barn. Dette er det barn, hvor det første bogstav matcher.
				//	System.out.println("cutString = "+cutString);
					//System.out.println("currentNode.getStr() = "+currentNode.getStr());
					for(int j = 0; j<currentNode.cList.size();j++)
					{
						if(currentNode.cList.get(j).getStr().charAt(0) == cutString.charAt(0) ) //hvis vi kigger ned i det rigtige barn.
						{
							currentNode = currentNode.cList.get(j);
							System.out.println("did i set the new currentNode?");
							cutString = cutString.substring(currentNode.getStr().length()); //jeg cutter strengen af, og kigger ned i dette barn.
							i = 0;
							break;
						}
					}

				}
			}
		}
	//	return null;
	}
	
	/*
	 * Denne metode retunerer et object array der indeholder 2 ting:
	 * Den sidste del af vores streng s som IKKE fandtes i træet.
	 * Den node vi stod i da vi returnerede.
	 */
	public Object[] amountAlreadyInTree(String s)
	{
		Object[] returnArray;
		returnArray = new Object[2];
		Node currentNode = root;
		String currentString;
		for(int i = 0; i<currentNode.amountOfChildren();i++)
		{
			
			if(currentNode.cList.get(i).getStr().charAt(0) == s.charAt(0) ) //vi har fundet den af børnene vi skal kigge i. Hvis den aldrig kommer her ind, går den bare ned og returnerer
			{
				String cutString = currentNode.cList.get(i).getStr();
				//jeg cutter af s, og hvis s.length() når 0, er strengen allerede i vores tree.
				for(int j = 0; j<s.length();j++)
				{
					if(cutString.length() == j-1 && s.length() > j-1) //vi er nået til en knude, og vi har stadig mere tilbage i vores s.
					{//jeg cutter først af s her, da det ellers fucker med mit loop, da jeg increaser j, men ændrer i størrelsen på arrayet.
						currentNode = currentNode.cList.get(i); //den node vi er nået til.
						i = 0; //jeg resetter i, da vi skal kigge alle børnene i denne node igennem
						s = s.substring(j);
						break;
					}
					
					//lav et tjek for, om jeg har nået enden af min streng s, og derfor skal returnere.
					//System.out.println("j = "+j);
					if(s.length() == j)
					{
						returnArray[0] = "";
						returnArray[1] = currentNode;
						
						return returnArray;
					}
					if(cutString.charAt(j) == s.charAt(j)) //hvis de 2 er ens kører jeg bare videre i mit loop.
					{
						continue;
					}
					else //if the chars dosent match :(
					{
						returnArray[0] = s.substring(j);
						returnArray[1] = currentNode;
						return returnArray;
					}

				}
			}

		}
		returnArray[0] = s;
		returnArray[1] = currentNode;
		return returnArray; //den retunerer det af s, som ikke var i træet.
	}
	public String algoSlowScan(String s)
	{
		String returnString = "";

		for(int i = 0; i <s.length(); i++)
		{
			if( slowScan(s.substring(i)) ) //tjek hvor meget af s, der allerede er i træet.
			{
				returnString = returnString + Character.toString(s.charAt(i));
			}
		}
		return returnString;
	}
	
	public boolean slowScan(String s)
	{
		return true;
	}
	
	public boolean slowScanOld(String s)
	{
		//TODO: der skal lige laves noget fix, i forhold til at man appender $ på alle strings.
		Node currentNode = root;
		String nodeString;
		//kig listen af børn igennem, og tag den der har samme bogstav som det vi er kommet til i s. 
		//jeg cutter det af min string, som der står i den node jeg står i. Derved kan jeg altid bruge den string igen, til at teste
		//på den næste node osv.

		for(int j = 0; j < 30; j++) //TODO: fix lige bound ( j < 30 = fail )
		{
			for(int i = 0; i<currentNode.amountOfChildren(); i++)
			{
				nodeString = currentNode.cList.get(i).getStr();
				//substring(i,j) sletter til og med i, men tager op til og med j.

				if(  nodeString.charAt(0) == s.charAt(0) ) //vi har fundet den node vi skal bruge.
				{				//jeg tjekker her, om de første n tegn i min s, er det samme som de n tegn i den node jeg står i.
					if( nodeString.startsWith(s.substring(0, nodeString.length())) )
					{
						s.substring(nodeString.length()); //jeg cutter det anden tegn der er i den node jeg står i fra.
						//update currentNode til det valgte barn. Nu kigger jeg på dennes børn.
						currentNode = currentNode.cList.get(i);
						break; //jeg breaker, og starter det indereste loop igen.
					}
				}
			}
		}
		if(s.length() == 0) //hele strengen er blevet cuttet væk, og derfor var den i træet.
		{
			return true;
		}
		else
		{
			return false;
		}
	}
	
	public String[] headTail(String s, int i)
	{
		String[] returnArray;
		returnArray = new String[2]; //pos 0 = head, pos 1 = tail
		
		if(i > s.length()) //burde smide en exception
		{
			System.out.println("i too large... faggot1");
			return returnArray;
		}
		//head er den længste LCP. Så jeg kan bare regne LCP i et loop, og så kun overskrive, hvis den nye værdi er større. Man skal regne LCP(i,j) for alle j < i
		int j = 1;
		String currentHead = "";
		String calcHead = "";
		while(j<i)
		{
			calcHead = LCP(s,j,i);
			if(calcHead.length() > currentHead.length())
			{
				currentHead = calcHead;
			}
			j++;
		}

		returnArray[0] = currentHead;
		returnArray[1] = s.substring(currentHead.length()); //dette er strengen - head.
		
		return returnArray;
	}
	
	public String LCP(String s, int i, int j) 
	{
		String xone = s.substring(i-1); //substring(i) cutter de første i bogstaver af strengen, men LCP starter med det bogstav der står på i. Derfor skal jeg bruge i-1
		String xtwo = s.substring(j-1);
		String returnString = "";

		for(int h=0; h < xone.length(); h++) //den skal bare køre op til en af stengenes længde. Den kommer højest sandsynligt til at break inden da.
		{
			if( xone.charAt(h) == xtwo.charAt(h) )
			{
				returnString = returnString + xone.charAt(h); //da de er ens, skal jeg bare tage char fra en af dem.
			}
			else
			{
				break; //hvis de ikke er ens, breaker jeg.
			}
		}
		return returnString;
	}
	
	public String head(String s, int i)
	{

		if(i > s.length()) //burde smide en exception
		{
			System.out.println("i too large... faggot(head)");
			return "";
		}
		//head er den længste LCP. Så jeg kan bare regne LCP i et loop, og så kun overskrive, hvis den nye værdi er større. Man skal regne LCP(i,j) for alle j < i
		int j = 1;
		String currentHead = "";
		String calcHead = "";
		while(j<i)
		{
			calcHead = LCP(s,j,i);
			if(calcHead.length() > currentHead.length())
			{
				currentHead = calcHead;
			}
			j++;
		}

		return currentHead;
	}
	
}